package com.hspedu;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

/**
 * @author 谷其昊
 * @version 1.0
 * @date 2022/4/19
 * @time 19:02
 */
public class HorseChessBoard {
    //定义属性
    private static int X = 6;
    private static int Y = 6;
    private static int[][] chessBoard = new int[X][Y];
    private static boolean[] visited = new boolean[X * Y];
    private static boolean finished = false;

    public static void main(String[] args) {
        for (int[] rows : chessBoard) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
        System.out.println("=========================");
        int row = 2, column = 2;
        long start = System.currentTimeMillis();
        traversalChessBoard(chessBoard,row-1,column-1,1);
        long end = System.currentTimeMillis();
        System.out.println("遍历耗时"+(end-start));
        for (int[] rows : chessBoard) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
    }

    public static void sort(ArrayList<Point> points){
        points.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return next(o1).size() - next(o2).size();
            }
        });
    }

    public static void traversalChessBoard(int[][] chessBoard, int row, int column, int step) {
        chessBoard[row][column] = step;
        //想一下邻接矩阵是一个 36*36
        //顶点表也是36个长度 row*X+column就是第几个节点，脑子里想一下邻接矩阵
        visited[row * X + column] = true;
        ArrayList<Point> points = next(new Point(column, row));
        sort(points);
        while (!points.isEmpty()) {
            Point point = points.remove(0);
            if (!visited[(int) (point.getY() * X + point.getX())]) {
                traversalChessBoard(chessBoard, point.y, point.x, step + 1);
            }
        }
        //如果没有遍历成功，就重置相应的值，然后回溯
        if (step < X * Y && !finished) {
            chessBoard[row][column] = 0;
            visited[row * X + column] = false;
        } else {
            finished = true;
        }
    }

    public static ArrayList<Point> next(Point current) {
        ArrayList<Point> points = new ArrayList<>();
        Point point = new Point();
        //判断5号位置能不能走
        if ((point.x = current.x - 2) >= 0 && (point.y = current.y - 1) >= 0) {
            points.add(new Point(point));
        }

        //判断6号位置能不能走
        if ((point.x = current.x - 1) >= 0 && (point.y = current.y - 2) >= 0) {
            points.add(new Point(point));
        }

        //判断7号位置能不能走
        if ((point.x = current.x + 1) < X && (point.y = current.y - 2) >= 0) {
            points.add(new Point(point));
        }

        //判断0号位置能不能走
        if ((point.x = current.x + 2) < X && (point.y = current.y - 1) >= 0) {
            points.add(new Point(point));
        }

        //判断1号位置能不能走
        if ((point.x = current.x + 2) < X && (point.y = current.y + 1) < Y) {
            points.add(new Point(point));
        }

        //判断2号位置能不能走
        if ((point.x = current.x + 1) < X && (point.y = current.y + 2) < Y) {
            points.add(new Point(point));
        }

        //判断3号位置能不能走
        if ((point.x = current.x - 1) >= 0 && (point.y = current.y + 2) < Y) {
            points.add(new Point(point));
        }

        //判断4号位置能不能走
        if ((point.x = current.x - 2) >= 0 && (point.y = current.y + 1) < Y) {
            points.add(new Point(point));
        }

        return points;
    }
}
